package com.zyk.leetcode;

import com.zyk.util.ListUtil;
import com.zyk.util.TreeUtil;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author zhangsan
 * @date 2021/4/9 14:45
 */
public class M0403 {

    // https://leetcode-cn.com/problems/list-of-depth-lcci/
    public static ListNode[] listOfDepth(TreeNode tree) {
        List<ListNode> list = new ArrayList<>();

        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(tree);

        while (!queue.isEmpty()) {
            ListNode lnh = new ListNode(-1);      // 这个链表节点的头
            ListNode cln = lnh;     // 当前链表节点
            for (int i = queue.size() - 1; i >= 0; i--) {
                TreeNode cur = queue.poll();
                cln.next = new ListNode(cur.val);
                if (cur.left != null) queue.add(cur.left);
                if (cur.right != null) queue.add(cur.right);
                cln = cln.next;
            }
            // 一层结束
            list.add(lnh.next);
        }
        ListNode[] ans = new ListNode[list.size()];
        for (int i = 0; i < list.size(); i++) {
            ans[i] = list.get(i);
        }
        return ans;
    }


    // for test
    public static void main(String[] args) {
        Integer[] nums = {1, 2, 3, 4, 5, null, 7, 8};
        TreeNode root = TreeUtil.generateTreeByArr(nums);

        ListNode[] ans = listOfDepth(root);
        for (int i = 0; i < ans.length; i++) {
            ListUtil.print(ans[i]);
        }


        /*TreeUtil.prePrint(root);
        System.out.println();*/
    }

}
